#pragma once
#include"vector_index.h"
#include<algorithm>
#include<vector>

template<class T>
struct EditorState{
	char signOfState;
	T stringOfState;
	EditorState(char signOfState, const T& stringOfState) :
		signOfState(signOfState), stringOfState(stringOfState){}
};

template<class iterator>
struct PackOfIterators{
	iterator firstBegin;
	iterator firstEnd;
	iterator secondBegin;
	iterator secondEnd;
	PackOfIterators(){}
	PackOfIterators(iterator firstBegin, iterator firstEnd,
		iterator secondBegin, iterator secondEnd) :
		firstBegin(firstBegin),
		firstEnd(firstEnd),
		secondBegin(secondBegin),
		secondEnd(secondEnd){}
};

template<class iterator>
PackOfIterators<std::reverse_iterator<iterator> > getReversedPackOfIterators(
	const PackOfIterators<iterator>& forwardIterator){
	std::reverse_iterator<iterator> firstBegin(forwardIterator.firstEnd), firstEnd(forwardIterator.firstBegin),
		secondBegin(forwardIterator.secondEnd), secondEnd(forwardIterator.secondBegin);
	return{ firstBegin, firstEnd, secondBegin, secondEnd };
}

namespace{
	
}

template<class iterator>
int maxPrefix(PackOfIterators<iterator> boundsOfContainers){
	int maxPrefixLength = 0;
	
	while (boundsOfContainers.firstBegin != boundsOfContainers.firstEnd &&
		boundsOfContainers.secondBegin != boundsOfContainers.secondEnd &&
		*(boundsOfContainers.firstBegin) == *(boundsOfContainers.secondBegin)){
		++boundsOfContainers.firstBegin;
		++boundsOfContainers.secondBegin;
		++maxPrefixLength;
	}
	return maxPrefixLength;
}


template<class iterator>
void executeFindingEditorDistanceStep(SignedArray<int>& situationOnDiagonals, int currentEditorDistance,
	const PackOfIterators<iterator>& boundsOfContainers){
	int firstSize = boundsOfContainers.firstEnd - boundsOfContainers.firstBegin;
	int secondSize = boundsOfContainers.secondEnd - boundsOfContainers.secondBegin;
	
	for (int diagonalNumber = -currentEditorDistance; diagonalNumber <= currentEditorDistance;
		diagonalNumber += 2){
		int currentX;
		if (diagonalNumber == -currentEditorDistance){
			currentX = situationOnDiagonals[diagonalNumber + 1];
		}
		else if (diagonalNumber == currentEditorDistance){
			currentX = situationOnDiagonals[diagonalNumber - 1] + 1;
		}
		else{
			currentX = std::max<int>(situationOnDiagonals[diagonalNumber - 1] + 1,
									 situationOnDiagonals[diagonalNumber + 1]);
		}
		int currentY = currentX - diagonalNumber;
		if (currentX <= firstSize && currentY <= secondSize){
			size_t maximalCurrentPrefix = maxPrefix(PackOfIterators<iterator>{ boundsOfContainers.firstBegin + currentX,
													boundsOfContainers.firstEnd,
													boundsOfContainers.secondBegin + currentY,
													boundsOfContainers.secondEnd });
			currentX += maximalCurrentPrefix;
			currentY += maximalCurrentPrefix;
		}
		situationOnDiagonals[diagonalNumber] = currentX;
	}
}

template<class iterator>
int getEditorDistance(const PackOfIterators<iterator>& boundsOfContainers){
	int firstSize = boundsOfContainers.firstEnd - boundsOfContainers.firstBegin;
	int secondSize = boundsOfContainers.secondEnd - boundsOfContainers.secondBegin;
	SignedArray<int> situationOnDiagonals(2 * (firstSize + secondSize) + 1, firstSize + secondSize);

	situationOnDiagonals[0] = maxPrefix(boundsOfContainers);
	int shift = firstSize - secondSize;
	if (situationOnDiagonals[shift] >= firstSize)
		return 0;

	for (int currentEditorDistance = 1; currentEditorDistance <= firstSize + secondSize; ++currentEditorDistance){
		executeFindingEditorDistanceStep(situationOnDiagonals, currentEditorDistance, boundsOfContainers);
		if (situationOnDiagonals[shift] >= firstSize){
			return currentEditorDistance;
		}
	}
	
}
